-- David Siegel, Jonathan Coveney, HW #8

module Set (Set (..), mkSet, toList,
            add, remove, union, empty, size, test
           ) where

import qualified List
import qualified Testing

------------------------------------------------------------
-- Public types
------------------------------------------------------------

newtype Eq a => Set a = Set [a]
  deriving Show

instance Eq a => Eq (Set a) where
  (Set []) == (Set b) = b == []
  (Set [a]) == b = if size b == 1 && element b a
                     then True
                     else False
  (Set (a:as)) == b = if element b a
                        then Set as == remove b a
                        else False


------------------------------------------------------------
-- Public method declaration
------------------------------------------------------------

-- Runs the appropriate tests for the module
test :: IO ()

-- Creates a new set from a list.
mkSet :: Eq a => [a] -> Set a

-- Adds an element to a set.
add :: Eq a => Set a -> a -> Set a

-- Removes an element from a set.
remove :: Eq a => Set a -> a -> Set a

-- The union of two sets
union :: Eq a => Set a -> Set a -> Set a

empty :: Eq a => Set a

size :: Eq a => Set a -> Int

toList :: Eq a => Set a -> [a]

element :: Eq a => Set a -> a -> Bool

------------------------------------------------------------
-- Public method definitions
------------------------------------------------------------

element (Set b) a = or $ map (a==) b

mkSet = Set . List.nub

add (Set es) e = if elem e es
                   then Set es
                   else Set (e:es)

remove (Set es) e = Set $ List.delete e es

union (Set as) (Set bs) = mkSet $ List.union as bs

empty = Set []

size (Set es) = List.length es

toList (Set es) = es

------------------------------------------------------------
-- Testing
------------------------------------------------------------

prop_mkset :: [Int] -> Bool
prop_mkset l = (Set (List.nub l)) == mkSet l

prop_add :: [Int] -> Int -> Bool
prop_add l e = mkSet (e:l) == add (mkSet l) e

prop_equal :: [Int] -> [Int] -> Bool
prop_equal l1 l2 = let f = (List.sort).(List.nub) in
                  if f l1 == f l2 then mkSet l1 == mkSet l2 else mkSet l1 /= mkSet l2

prop_size  :: [Int] -> Bool
prop_size t = ((List.length).(List.nub)) t == (size.mkSet) t

prop_empty :: Int -> Bool
prop_empty t = remove (mkSet [t]) t == empty

prop_union :: [Int] -> [Int] -> Bool
prop_union t1 t2 = mkSet (t1 `List.union` t2) == mkSet t1 `union` mkSet t2

prop_toList :: [Int] -> Bool
prop_toList t = ((List.sort).toList.mkSet) t == ((List.sort).(List.nub)) t

prop_element :: [Int] -> Bool
prop_element t = if t == [] then True else element (mkSet t) (head t)

test = do Testing.quickcheck prop_mkset
          Testing.quickcheck prop_add
          Testing.quickcheck prop_equal
          Testing.quickcheck prop_size
          Testing.quickcheck prop_empty
          Testing.quickcheck prop_union
          Testing.quickcheck prop_toList
          Testing.quickcheck prop_element